iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 20
1
自我挑戰組

Verilog 從放棄到有趣系列 第 20

[Day20]泡沫排序法

  • 分享至 

  • xImage
  •  

今天想來跟大家分享泡沫排序法(Bubble Sort),先來看一下維基百科的pseudo code:

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

可以看到如果上面這樣排序的話,需要(n^2)的時間,但如果寫成電路的話,只需要O(n)時間,怎麼會這麼神奇呢,其實有點像是空間換取時間的感覺.

由於電路可以利用多個比較器,一次比較多個元素,有點像平行處理的感覺,所以只要發現能夠平行處理的資料,且在資源允許的情況下,當然希望能越快越好囉.

大概說明一下演算法,
有幾個元素就做幾個回合,所以需要一個counter計數回合,
單數回合做[0,1][2,3]…比較,如果大於就swap,
雙數回合做[1,2][3,4]…比較,如果大於就swap,
有幾個要比較的元素就比較幾個回合.

這邊簡單用一張圖說一下演算法:

https://ithelp.ithome.com.tw/upload/images/20171231/20107543O3OEgRAXGu.png

code:

assign out_valid = (sort_cnt == 4);

 always@(posedge clk)begin
         if(rst)
            sort_idx <= 0;
          else if(in_valid)
            sort_idx <= ~sort_idx;
       end
       

always@(posedge clk)begin
  if(rst)
  sort_cnt <= 0;
else if(in_valid)
  sort_cnt <= (sort_cnt == 4) ? sort_cnt : sort_cnt+1;
end

always@(posedge clk)begin
  if(in_valid & ~sort_idx)begin
    for(i=0;i<4;i=i+2)begin
      array[i  ] <= (array[i] > array[i+1]) ? array[i+1] : array[i  ];
      array[i+1] <= (array[i] > array[i+1]) ? array[i  ] : array[i+1];
    end
  end
  else if(in_valid & sort_idx)begin
    for(i=1;i<3;i=i+2)begin
      array[i  ] <= (array[i] > array[i+1]) ? array[i+1] : array[i  ];
      array[i+1] <= (array[i] > array[i+1]) ? array[i  ] : array[i+1];
    end
  end

波形:

https://ithelp.ithome.com.tw/upload/images/20171231/20107543KdiEXRmigA.jpg

上面這張圖是做四個元素的排序,所以只需4個回合就能運算完,因為比較器能共用的關係,所以只要總元素除以2,這邊來說只需2個比較器即可,是不是跟想像中的泡沫排序有點不一樣呢,這就是電路有趣的部分,很多演算法只要發現規則,就會有不一樣的結果.


上一篇
[Day19]何謂Latch?
下一篇
[Day21]插入排序法
系列文
Verilog 從放棄到有趣30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言